import java.util.Map;
import java.util.TreeMap;

public class BinarySearchTree {


    public static class Node {
        int key;
        Node left;
        Node right;
        public Node(int key) {
            this.key = key;
        }
    }

    Node root=null;



    public static void main(String[] args) {

        BinarySearchTree binarySearchTree=new BinarySearchTree();

        Node node1=new Node(1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        Node node4=new Node(4);
        Node node5=new Node(5);
        Node node6=new Node(6);
        Node node7=new Node(7);
        Node node8=new Node(8);
        Node node9=new Node(9);
        binarySearchTree.root=node5;

        node5.left=node2;
        node2.left=node1;
        node2.right=node3;
        node3.right=node4;
        node5.right=node7;
        node7.left=node6;
        node7.right=node8;
        node8.right=node9;

        binarySearchTree.remove(7);

    }


    public Node search(int key) {
        Node cur = root;
        while (cur != null) {

            if (cur.key == key) {
                return cur;
            } else if (cur.key > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }

        return null;
    }


    public boolean remove(int key){

        Node cur=root;
        Node prev=null;
        while(cur!=null){

            if(cur.key==key){
                break;
            }else if(cur.key>key) {
                prev=cur;
                cur=cur.left;
            }else {
                prev=cur;
                cur=cur.right;
            }
        }


        if(cur==null) return false;

        Node tail=cur.left;

        if(tail==null){
            if(prev.right==cur){
                prev.right=cur.right;
                return true;
            }else {
                prev.left=cur.right;
                return true;

            }
        }

        if(tail.right==null){
            cur.key=tail.key;
            cur.left=null;
            return true;
        }



        while(tail.right!=null){
            prev=tail;
            tail=tail.right;

        }

        //替换交换删除法

        cur.key=tail.key;

        prev.right=null;

        return true;

    }

    public boolean insert(int key) {
        if (root == null) {
            root = new Node(key);
            return true;
        }
        Node cur = root;

        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                return false;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        Node node = new Node(key);
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return true;
    }


    public static void TestMap() {
        Map<String, String> m = new TreeMap<>();
// put(key, value):插入key-value的键值对
// 如果key不存在，会将key-value的键值对插入到map中,返回null
        m.put("林冲", "豹子头");
        m.put("鲁智深", "花和尚");
        m.put("武松", "行者");
        m.put("宋江", "及时雨");
        String str = m.put("李逵", "黑旋风");
        System.out.println(m.size());
        System.out.println(m);
// put(key,value): 注意key不能为空，但是value可以为空
// key如果为空，会抛出空指针异常
//m.put(null, "花名");
        str = m.put("无名", null);
        System.out.println(m.size());
// put(key, value):
// 如果key存在，会使用value替换原来key所对应的value，返回旧value
        str = m.put("李逵", "铁牛");
// get(key): 返回key所对应的value
// 如果key存在，返回key所对应的value
// 如果key不存在，返回null
        System.out.println(m.get("鲁智深"));
        System.out.println(m.get("史进"));
//GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
        System.out.println(m.getOrDefault("李逵", "铁牛"));
        System.out.println(m.getOrDefault("史进", "九纹龙"));
        System.out.println(m.size());
//containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
// 按照红黑树的性质来进行查找
// 找到返回true，否则返回false
        System.out.println(m.containsKey("林冲"));
        System.out.println(m.containsKey("史进"));
// containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
// 找到返回true，否则返回false
        System.out.println(m.containsValue("豹子头"));
        System.out.println(m.containsValue("九纹龙"));
// 打印所有的key
// keySet是将map中的key防止在Set中返回的

        for (String s : m.keySet()) {
            System.out.print(s + " ");
        }
        System.out.println();
// 打印所有的value
// values()是将map中的value放在collect的一个集合中返回的
        for (String s : m.values()) {
            System.out.print(s + " ");
        }
        System.out.println();
// 打印所有的键值对
// entrySet(): 将Map中的键值对放在Set中返回了
        for (Map.Entry<String, String> entry : m.entrySet()) {
            System.out.println(entry.getKey() + "--->" + entry.getValue());
        }
        System.out.println();
    }

    }


